package graphmanip;

import guiobjects.Observation;

import java.awt.Point;
import java.util.ArrayList;

import commonfunctions.Matrix;

/**
 * This class was created to enable easy manipulation of a graph. Different functions can be used to
 * collapse nodes together and to remove edges. It fully implements the coarsening-uncoarsening 
 * algorithm we discussed. 
 * 
 * @author Trevor Terris
 *
 */
public class Graph 
{
	private Matrix myWeights;
	private Graph myLessCoarseGraph;
	private ArrayList<ArrayList<Integer>> mySmallerToLargerGraphMappings;
	private ArrayList<ArrayList<Integer>> myTracks;
	/**
	 * Creates the original graph, using the weights and the list of observations.
	 * 
	 * @param weights
	 * @param observations
	 */
	public Graph(Matrix weights, ArrayList<Observation> observations)
	{
		myWeights = new Matrix(weights);
		myTracks = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < observations.size(); i++)
		{
			ArrayList<Integer> entry = new ArrayList<Integer>();
			entry.add(i);
			myTracks.add(entry);
		}
		//makeContradictoryEdgesNegative(observations);
		myLessCoarseGraph = null;
		mySmallerToLargerGraphMappings = null;
	}
	/**
	 * Private method, used for creating the less coarse graph when coarsening.
	 * 
	 * @param g
	 */
	private Graph(Graph g)
	{
		myWeights = g.myWeights;
		myLessCoarseGraph = g.myLessCoarseGraph;
		mySmallerToLargerGraphMappings = g.mySmallerToLargerGraphMappings;
		myTracks = g.myTracks;
	}
	/**
	 * Using a provided algorithm, removes some edges from the graph.
	 * 
	 * @param thinningAlgo
	 */
	public void thinGraph(ThinningMethod thinningAlgo)
	{
		ArrayList<Point> edgesToRemove = thinningAlgo.thinGraph(myWeights);
		for (int i = 0; i < edgesToRemove.size(); i++)
			deleteEdge(edgesToRemove.get(i).x, edgesToRemove.get(i).y);
	}
	/**
	 * Deletes an edge going from the node start to the node end, recursively removing the edge 
	 * from all less-coarse versions of the graph. If the edge is negative, it's left alone.
	 * 
	 * @param start
	 * @param end
	 */
	private void deleteEdge(int start, int end)
	{
		if (myWeights.get(start, end) > 0.0)
			myWeights.set(0.0, start, end);
		if (!isUncoarsened())
		{
			ArrayList<Integer> from = mySmallerToLargerGraphMappings.get(start);
			ArrayList<Integer> to = mySmallerToLargerGraphMappings.get(end);
			for (int i = 0; i < from.size(); i++)
			{
				for (int j = 0; j < to.size(); j++)
				{
					myLessCoarseGraph.deleteEdge(from.get(i), to.get(j));
				}
			}
		}
	}
	/**
	 * Uncoarsens the graph, resetting the weights and the tracks to the stored less coarse version.
	 */
	public void uncoarsen()
	{
		if (!isUncoarsened())
		{
			mySmallerToLargerGraphMappings = myLessCoarseGraph.mySmallerToLargerGraphMappings;
			myTracks = myLessCoarseGraph.myTracks;
			myWeights = myLessCoarseGraph.myWeights;
			myLessCoarseGraph = myLessCoarseGraph.myLessCoarseGraph;
		}
	}
	/**
	 * Function to determine whether the graph is fully uncoarsened. 
	 * 
	 * @return true if the graph is fully uncoarsened, false if not.
	 */
	public boolean isUncoarsened()
	{
		return myLessCoarseGraph == null;
	}
	/**
	 * Using a provided algorithm, reduces the number of nodes in the graph.
	 * 
	 * @param collapseAlgo
	 */
	public void collapseGraph(CollapsingMethod collapseAlgo, boolean shouldRemoveDeadEnds)
	{
		Matrix newWeights = new Matrix(myWeights);
		int[] oldToNewMapping = new int[myWeights.length()];
		int[] newToOldMapping = new int[myWeights.length()];
		for (int i = 0; i < oldToNewMapping.length; i++)
		{
			oldToNewMapping[i] = i;
			newToOldMapping[i] = i;
		}
		ArrayList<Integer> unconnected = new ArrayList<Integer>();
		if (shouldRemoveDeadEnds)
		{
			unconnected = unconnectedNodes();
			int offset = 0;
			for (int i = 0; i < oldToNewMapping.length; i++)
			{
				if (!unconnected.contains(i))
					oldToNewMapping[i] = i - offset;
				else
				{
					oldToNewMapping[i] = -1;
					offset++;
				}
			}
			newToOldMapping = new int[myWeights.length() - unconnected.size()];
			for (int i = 0; i < oldToNewMapping.length; i++)
			{
				if (oldToNewMapping[i] != -1)
					newToOldMapping[oldToNewMapping[i]] = i;
			}
			newWeights = new Matrix(myWeights.length() - unconnected.size());
			for (int i = 0; i < myWeights.length(); i++)
			{
				for (int j = 0; j < myWeights.length(); j++)
				{
					newWeights.set(myWeights.get(i, j), oldToNewMapping[i], oldToNewMapping[j]);
				}
			}
			System.out.println(unconnected.size() + " dead ends.");
		}
		//sets up the next depth of the graph, making this graph the less coarse version.
		myLessCoarseGraph = new Graph(this);
		ArrayList<ArrayList<Integer>> nextTracks = new ArrayList<ArrayList<Integer>>(myTracks);
		myTracks = nextTracks;
		mySmallerToLargerGraphMappings = new ArrayList<ArrayList<Integer>>();
		
		//gets the list of lists. If two nodes are in the same list, then the will be reduced to one node.
		ArrayList<ArrayList<Integer>> nodesToCollapse = collapseAlgo.collapse(newWeights);
		
		for (int i = 0; i < nodesToCollapse.size(); i++)
		{
			for (int j = 0; j < nodesToCollapse.get(i).size(); j++)
				nodesToCollapse.get(i).set(j, newToOldMapping[nodesToCollapse.get(i).get(j)]);
		}
		
		//creates the mapping; ultimately, this will map the nodes in the larger graph to the new, smaller one.
		int[] mapping = new int[myWeights.length()];
		for (int i = 0; i < mapping.length; i++)
			mapping[i] = i;
		//iterates through all lists
		for (int i = 0; i < nodesToCollapse.size(); i++)
		{
			if (nodesToCollapse.get(i).size() > 1)
			{
				//finds the minimum value in the list....
				int min = myWeights.length();
				for (int j = 0; j < nodesToCollapse.get(i).size(); j++)
				{
					if (nodesToCollapse.get(i).get(j) < min)
						min = nodesToCollapse.get(i).get(j);
				}
				//...and maps each node to the node that minimum maps to.
				for (int j = 0; j < nodesToCollapse.get(i).size(); j++)
				{
					mapping[nodesToCollapse.get(i).get(j)] = mapping[min];
				}
			}
		}
		//Now we have some situations where a maps to b, b maps to c, and c maps to d. In this loop,
		//we map a, b, and c to d. d is mapped to itself; we chose the minimum value earlier so we 
		//wouldn't get closed loops.
		for (int i = 0; i < mapping.length; i++)
		{
			int currentVal = i;
			while (mapping[currentVal] != currentVal)
				currentVal = mapping[currentVal];
			mapping[i] = currentVal;
		}
		//now, we add the contents of each track to the track that they are being concentrated to.
		for (int i = 0; i < mapping.length; i++)
		{
			if (mapping[i] != i)
				nextTracks.get(mapping[i]).addAll(nextTracks.get(i));
		}
		//now we're removing the collapsed nodes. The offset is needed because the index of the 
		//list to remove decreases as we removed lists before it.
		ArrayList<Integer> listOfNodeStarts = new ArrayList<Integer>();
		int offset = 0;
		for (int i = 0; i < mapping.length; i++)
		{
			if (mapping[i] != i)
			{
				nextTracks.remove(i - offset);
				offset++;
			}
			else
				listOfNodeStarts.add(i);
		}
		//the next five lines create an ArrayList of ArrayLists of Integers, which will be used to calculate
		//the weights of the graph, by summing up the edges. For example, if the weight from node a to b is e,
		//and the weight from c to d is f, and a is collapsed with c and b is collapsed with d, then the new
		//graph has two nodes, (a,c) and (b,d), with weight e + f.
		ArrayList<ArrayList<Integer>> listOfGroupedNodes = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < listOfNodeStarts.size(); i++)
			listOfGroupedNodes.add(new ArrayList<Integer>());
		for (int i = 0; i < mapping.length; i++)
			listOfGroupedNodes.get(listOfNodeStarts.indexOf(mapping[i])).add(i);
		//create the new matrix, then set the weights.
		Matrix newMatrix = new Matrix(listOfNodeStarts.size());
		for (int i = 0; i < listOfGroupedNodes.size(); i++)
		{
			for (int j = i + 1; j < listOfGroupedNodes.size(); j++)
			{
				for (int k = 0; k < listOfGroupedNodes.get(i).size(); k++)
				{
					for (int l = 0; l < listOfGroupedNodes.get(j).size(); l++)
					{
						int first = Math.min(listOfGroupedNodes.get(i).get(k), listOfGroupedNodes.get(j).get(l));
						int second = Math.max(listOfGroupedNodes.get(i).get(k), listOfGroupedNodes.get(j).get(l));
						newMatrix.set(newMatrix.get(i, j) + myWeights.get(first, second), i, j);
					}
				}
			}
		}
		//Sets up the graph mapping for the coarse version.
		for (int i = 0; i < listOfNodeStarts.size(); i++)
		{
			ArrayList<Integer> toAdd = new ArrayList<Integer>();
			toAdd.add(listOfNodeStarts.get(i));
			mySmallerToLargerGraphMappings.add(toAdd);
		}
		for (int i = 0; i < mapping.length; i++)
		{
			if (mapping[i] != i)
			{
				int indexToAdd = listOfNodeStarts.indexOf(mapping[i]);
				mySmallerToLargerGraphMappings.get(indexToAdd).add(i);
			}
		}
		//sets the coarser edges
		myWeights = newMatrix;
	}
	/**
	 * Checks to see if the graph is partitioned fully; returns true if there are only negative-weight edges,
	 * so grouping nodes together would only reduce the value of the graph.
	 * 
	 * @return
	 */
	public boolean isFinished()
	{
		for (int i = 0; i < myWeights.length(); i++)
		{
			for (int j = 0; j < myWeights.length(); j++)
			{
				if (myWeights.get(i, j) > 0.0)
					return false;
			}
		}
		
		return true;
	}
	/**
	 * Once the graph is reduced, uses the tracks obtained from the collapsed nodes to create the graph of 
	 * tracked values.
	 * 
	 * @return
	 */
	public Matrix trackedGraph()
	{
		ArrayList<ArrayList<Integer>> newTracks = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < myTracks.size(); i++)
		{
			ArrayList<Integer> toAdd = new ArrayList<Integer>();
			for(int j = 0; j < myTracks.get(i).size(); j++)
				toAdd.add(myTracks.get(i).get(j));
			newTracks.add(toAdd);
		}
		int size = 0;
		for (int i = 0; i < newTracks.size(); i++)
			size += newTracks.get(i).size();
		
		Matrix toReturn = new Matrix(size);
		
		for (int i = 0; i < newTracks.size(); i++)
		{
			int lastNum = -1;
			int sizeOfTrack = newTracks.get(i).size();
			for (int j = 0; j < sizeOfTrack; j++)
			{
				int minIndex = 0;
				for (int k = 0; k < newTracks.get(i).size(); k++)
					minIndex = (newTracks.get(i).get(k) > newTracks.get(i).get(minIndex))?minIndex:k;
				if (lastNum != -1)
					toReturn.set(true, lastNum, newTracks.get(i).get(minIndex));
				lastNum = newTracks.get(i).remove(minIndex);
			}
		}
		
		return toReturn;
	}
	/**
	 * Returns the size of the current graph.
	 * 
	 * @return
	 */
	public int size()
	{
		return myWeights.length();
	}
	public ArrayList<Integer> unconnectedNodes ()
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		for (int i = 0; i < myWeights.length(); i++)
		{
			boolean hasPositive = false;
			for (int j = 0; j < myWeights.length(); j++)
			{
				if (myWeights.get(i, j) > 0.0 || myWeights.get(j, i) > 0.0)
				{
					hasPositive = true;
					break;
				}
			}
			if (!hasPositive)
				toReturn.add(i);
		}
		return toReturn;
	}
}
